package pers.tz.题目.leetcode;

import java.util.*;

/**
 * @author irony
 * @date 2024-03-14
 */
public class 面试题_08_08_有重复字符串的排列组合 {
// 有重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合。
//
//示例1:
// 输入：S = "qqe"
// 输出：["eqq","qeq","qqe"]
//
//示例2:
// 输入：S = "ab"
// 输出：["ab", "ba"]
//提示:
//
//字符都是英文字母。
//字符串长度在[1, 9]之间。
    public static void main(String[] args) {
        System.out.println(Arrays.toString(permutation2("abc")));
    }

    // 最优解
    public static String[] permutation2(String S) {
        List<String> ans = new ArrayList<>();
        process2(S.toCharArray(), 0, ans);
        return ans.toArray(new String[0]);
    }

    private static void process2(char[] str, int index, List<String> ans) {
        if (index == str.length) {
            ans.add(String.valueOf(str));
            return;
        }

        for (int i = index; i < str.length; i++) {
            swap(str, index, i);
            process2(str, index + 1, ans);
            swap(str, index, i);
        }
    }

    private static void swap(char[] str, int i, int j) {
        char c = str[i];
        str[i] = str[j];
        str[j] = c;
    }

    // 可行解
    public static String[] permutation1(String S) {
        Set<String> ans = new HashSet<>();
        char[] charArray = S.toCharArray();
        List<Character> rest = new ArrayList<>();
        for (char c : charArray) {
            rest.add(c);
        }

        process1(rest, "", ans);

        return ans.toArray(new String[0]);
    }

    public static void process1(List<Character> rest, String path, Set<String> ans) {
        if (rest.isEmpty()) {
            ans.add(path);
            return;
        }

        int size = rest.size();
        for (int i = 0; i < size; i++) {
            char cur = rest.remove(i);
            process1(rest, path + cur, ans);
            // 恢复现场
            rest.add(i, cur);
        }
    }
}
